//假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说： 
//
// 实现 track(int x) 方法，每读入一个数字都会调用该方法； 
//
// 实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。 
//
// 注意：本题相对原题稍作改动 
//
// 示例： 
//
// 
//输入：
//["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
//[[], [1], [0], [0]]
//输出：
//[null,0,null,1]
// 
//
// 提示： 
//
// 
// x <= 50000 
// track 和 getRankOfNumber 方法的调用次数均不超过 2000 次 
// 
//
// Related Topics 设计 树状数组 二分查找 数据流 👍 50 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-02 23:58:06
 * @description 面试题 10.10.数字流的秩
 */
public class RankFromStreamLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 RankFromStreamLcci fun=new RankFromStreamLcci();


	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class StreamRank {
    //TreeMap
//    TreeMap<Integer, Integer> treeMap;
//
//    public StreamRank() {
//        treeMap = new TreeMap<>();
//    }
//    //track 平均时间复杂度  ologM
//    public void track(int x) {
//        treeMap.put(x, treeMap.getOrDefault(x, 0) + 1);
//    }
//    //时间复杂度o m
//    public int getRankOfNumber(int x) {
//        int rank = 0;
//        // subMap 返回指定范围的treemap  headmap返回包含小于key的
//        //tailmap返回包含所有大于等于指定的
//
//
//        for (int v : treeMap.headMap(x, true).values()) {
//            rank += v;
//        }
//        return rank;
//    }




    // 自平衡二叉查找树AVL 时间track ologm  空间 on

//    DuplicatedLEAVLTree<Integer> tree;
//
//    public StreamRank() {
//        tree = new DuplicatedLEAVLTree<>();
//    }
//
//    public void track(int x) {
//        tree.add(x);
//    }
//
//    public int getRankOfNumber(int x) {
//        return tree.headTreeSize(x, true);
//    }
//
//    /**
//     * A avl tree that allows duplicated elements. It is rapid to get
//     * the count of the elements that are less than or equal to the given value.
//     */
//    public class DuplicatedLEAVLTree<T extends Comparable<T>> {
//
//        private Node root;
//
//        private class Node {
//
//            public T val;
//
//            public int height = 1, size = 1, count = 1;
//
//            public Node parent, left, right;
//
//            public Node(T val, Node parent) {
//                this.val = val;
//                this.parent = parent;
//            }
//
//            public int refreshSize() {
//                size = size(left) + size(right) + count;
//                return size;
//            }
//
//            public int refreshHeight() {
//                height = Math.max(height(left), height(right)) + 1;
//                return height;
//            }
//
//            public void refreshSizeAndHeight() {
//                refreshSize();
//                refreshHeight();
//            }
//
//            public int getBalanceFactor() {
//                return height(left) - height(right);
//            }
//
//        }
//
//        /**
//         * Add an element to the tree.
//         * @param val
//         * @return existed or not
//         */
//        public boolean add(T val) {
//            Node node = search(val), parent = null;
//            if (node != null) {
//                node.count++;
//                rebalance(node);
//                return true;
//            }
//
//            node = root;
//            while (node != null) {
//                parent = node;
//                node = val.compareTo(node.val) < 0 ? node.left : node.right;
//            }
//
//            if (parent == null) {
//                root = new Node(val, parent);
//            } else if (val.compareTo(parent.val) > 0) {
//                parent.right = new Node(val, parent);
//                rebalance(parent);
//            } else {
//                parent.left = new Node(val, parent);
//                rebalance(parent);
//            }
//            return false;
//        }
//
//        /**
//         * Get the count of the elements that are less than (or equals to, if
//         * inclusive is {@code true}) the given value.
//         * @param val
//         * @param inclusive
//         * @return {@code count}
//         */
//        public int headTreeSize(T val, boolean inclusive) {
//            Node node = floor(val);
//            if (node == null) {
//                return 0;
//            }
//
//            int ans = size(root) - size(root.right);
//            Node pointer = root;
//            while (pointer != node) {
//                if (node.val.compareTo(pointer.val) < 0) {
//                    ans -= pointer.count + size(pointer.left.right);
//                    pointer = pointer.left;
//                } else {
//                    ans += pointer.right.count + size(pointer.right.left);
//                    pointer = pointer.right;
//                }
//            }
//
//            if (!inclusive && node.val.equals(val)) {
//                ans -= node.count;
//            }
//            return ans;
//        }
//
//        /**
//         * Searches the node for the value.
//         * @param val
//         * @return {@code null} or {@code node}
//         */
//        public Node search(T val) {
//            Node node = root;
//            while (node != null && !node.val.equals(val)) {
//                node = node.val.compareTo(val) > 0 ? node.left : node.right;
//            }
//            return node;
//        }
//
//        private void rebalance(Node node) {
//            while (node != null) {
//                int balanceFactor = node.getBalanceFactor();
//                if (balanceFactor == 2) {
//                    if (height(node.left.left) < height(node.left.right)) {
//                        rotateLeft(node.left);
//                    }
//                    node = rotateRight(node);
//                } else if (balanceFactor == -2) {
//                    if (height(node.right.right) < height(node.right.left)) {
//                        rotateRight(node.right);
//                    }
//                    node = rotateLeft(node);
//                }
//
//                node.refreshSizeAndHeight();
//                if (node.parent == null) {
//                    root = node;
//                }
//                node = node.parent;
//            }
//        }
//
//        private Node rotateLeft(Node node) {
//            Node right = node.right;
//            node.right = right.left;
//            if (node.right != null) {
//                node.right.parent = node;
//            }
//            right.left = node;
//            right.parent = node.parent;
//            node.parent = right;
//            if (right.parent != null) {
//                if (right.parent.left == node) {
//                    right.parent.left = right;
//                } else {
//                    right.parent.right = right;
//                }
//            }
//
//            node.refreshSizeAndHeight();
//            right.refreshSizeAndHeight();
//            return right;
//        }
//
//        private Node rotateRight(Node node) {
//            Node left = node.left;
//            node.left = left.right;
//            if (node.left != null) {
//                node.left.parent = node;
//            }
//            left.right = node;
//            left.parent = node.parent;
//            node.parent = left;
//            if (left.parent != null) {
//                if (left.parent.left == node) {
//                    left.parent.left = left;
//                } else {
//                    left.parent.right = left;
//                }
//            }
//
//            node.refreshSizeAndHeight();
//            left.refreshSizeAndHeight();
//            return left;
//        }
//
//        private Node floor(T val) {
//            Node node = root;
//            Node ans = null;
//            while (node != null && !node.val.equals(val)) {
//                if (node.val.compareTo(val) > 0) {
//                    node = node.left;
//                } else {
//                    ans = node;
//                    node = node.right;
//                }
//            }
//            return node == null ? ans : node;
//        }
//
//        private int height(Node node) {
//            return node == null ? 0 : node.height;
//        }
//
//        private int size(Node node) {
//            return node == null ? 0 : node.size;
//        }
//    }
//
//	List<Integer> nums;
//	//二分+插入排序
//	public StreamRank() {
//		nums = new ArrayList<>();
//	}
//
//	public void track(int x) {
//		int index = getRankOfNumber(x); //插入的位置刚好就是第一个大于x的下标
//		nums.add(index, x);
//	}
//
//	public int getRankOfNumber(int x) { //小于等于x的值的个数，等效找第一个大于x的下标
//		int n = nums.size();
//		if (n == 0) return 0;
//		//找第一个大于x的下标
//		int l = 0, r = n;
//		while (l < r) {
//			int mid = l + r >> 1;
//			if (nums.get(mid) <= x) l = mid + 1;
//			else if (nums.get(mid) > x) r = mid;
//		}
//		return l;
//	}

	// 树状数组
	int[] tree;
	int n = 50001;
	int lowbit(int x) {
		return x & -x;
	}
	int query(int x) {
		int ans = 0;
		for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
		return ans;
	}

	void add(int x, int u) {
		for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
	}

	public StreamRank() {
		tree = new int[n + 1];
	}

	public void track(int x) {
		add(x + 1, 1);
	}

	public int getRankOfNumber(int x) {
		return query(x + 1);
	}



}

/**
 * Your StreamRank object will be instantiated and called as such:
 * StreamRank obj = new StreamRank();
 * obj.track(x);
 * int param_2 = obj.getRankOfNumber(x);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
